package com.wk.arth.od;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Stack;

/**
 * 贪心算法之删数字
 * 给定一个由纯数字组成以字符串表示的数值，现要求字符串中的每个数字最多只能出现2次，超过后需要删除，删除某个重复的数字后，其它数字相对位置保持不变。
 *
 * 如："34533"，数字3重复超过2次，需要删除一个3，删除第一个3后获得最大数值"4533"
 *
 * 输入描述：第一行是纯数字组成的字符串
 * 输出描述：经过删除后的最大数值，以字符串表示
 *
 * 示例1
 * 输入：34533
 * 输出：4533
 *
 * 示例2
 * 输入：5445795045
 * 输出：5479504
 * @author wukai
 * @date 2023/4/19 19:34
 *
 * 利用栈来解决
 * 定义2个map unused 和 reverse
 * unused 每个数字剩余可用个数
 * reverse 每个数字已保留的个数
 */
public class Shan_shu_zi {
    public static void main(String[] args) {
        System.out.println(solve("65432111"));
    }
    public static String solve(String input){
        HashMap<Character,Integer> unused = new HashMap<>();
        HashMap<Character,Integer> reverse = new HashMap<>();
        char[] arr = input.toCharArray();
        for (char c : arr) {
            int cur = unused.getOrDefault(c,0);
            unused.put(c,cur+1);
            reverse.putIfAbsent(c,0);
        }
        LinkedList<Character> stack = new LinkedList<>();
        for (int i=0;i<arr.length;i++){
            char c = arr[i];
            // 已经保留2个了，后续可以丢弃
            if(reverse.get(c) == 2){
                unused.put(c,unused.get(c)-1);
                continue;
            }
            // 比较当前元素c 和 栈顶元素top,如果c> top ，考虑将top弹出
            while (stack.size()>0){
                char top = stack.getLast();
                // 如果栈顶元素top被弹出后，已保留的top字符+未使用的top字符数量之和>=2
                if(c > top && unused.get(top)+reverse.get(top)-1>=2){
                    stack.removeLast();
                    reverse.put(top,reverse.get(top)-1);
                }else{
                    break;
                }
            }
            stack.add(c);
            reverse.put(c, reverse.get(c)+1);
            unused.put(c, unused.get(c)-1);
        }
        StringBuilder builder = new StringBuilder();
        for (Character character : stack) {
            builder.append(character);
        }
        return builder.toString();
    }
}
